All Questions
Tagged with ds.algorithmsgraph-algorithms
340 questions
1vote
0answers
63views
Repeated subgraph matchings with disjoint images
I'm having trouble finding the name (if it exists) of a particular specialization of the subgraph enumeration problem where subgraphs isomorphisms have disjoint images. More specifically, let $G = (V, ...
4votes
1answer
205views
About the negative real weight SSSP in $\tilde{O}(m n^{8/9})$ by Fineman
In his sensational paper “Single-Source Shortest Paths with Negative Real Weights in $\tilde{O}(m n^{8/9})$ Time”, (STOC ’24), Jeremy T. Fineman successfully broke the long-standing bound of negative ...
- 143
0votes
0answers
49views
Min cost perfect matching, but with conflicting edge pairs
Consider the following variant of min-weight perfect matching. We are given a graph $G = (V,E)$ with non-negative weights on the edges. We are also given a collection of pairs of edges $P \subseteq E \...
- 649
4votes
5answers
2kviews
Are there any examples of exponential algorithms that use a polynomial-time algorithm for a special case as a subroutine (exponentially many times)?
There are many examples of exponential algorithms that use polynomial algorithms for special cases as subroutines. Still, I was hoping to see one that uses a well-known polynomial algorithm for a ...
- 245
2votes
0answers
145views
Counterexample for the 1-optimal matching algorithm in Gabow's and Tarjan's paper on scaling algorithms for networks
Context I am reading Faster scaling algorithms for network problems by Gabow and Tarjan where I am researching part 2: "Matching and extensions". However, I am a bit confused with the ...
- 21
4votes
1answer
157views
Min-cost perfect matching, but must pick exactly k special edges. Is it NP-hard?
I'd like to know if the following generalization of min-cost perfect matching is NP-hard. As usual, we are given a graph $G = (V,E)$ with costs on edges $c: E \to \mathbb{R}_{\geq 0}$. In addition, ...
- 649
0votes
1answer
61views
Question about claw-free graphs
Let $G$ be a claw-free graph, and let $x,y,z,u$ be distinct vertices of $G$. Is the following possible in $G$ ? There are three induced paths through $u$: between $y$ and $z$ (i.e., $y \...
- 103
3votes
1answer
90views
What is the fastest algorithm for computing exact network reliability?
In the network reliability problem, we are given an undirected graph $G$ on $n$ vertices and a parameter $p\in (0,1)$, and are tasked with determining the probability that $G$ becomes disconnected (i....
- 696
2votes
1answer
131views
Maximum cardinality disjoint cycle cover in undirected graphs
I call a maximum cardinality disjoint cycle cover of a graph a vertex-disjoint cycle cover containing the maximum possible number of cycles in the graph. What is known about the complexity of this ...
- 948
1vote
1answer
79views
What is known about the complexity of Network Diversion?
In the Network Diversion problem, we are given an undirected graph $G$ on $n$ vertices, with specified nodes $s$ and $t$ and specified edge $e$, and a positive integer $k$, and are tasked with ...
- 696
5votes
1answer
101views
Independent set queries with preprocessing
Suppose we have a sparse undirected graph $G = (V, E)$ with $|E| = O(|V|)$, and we want to process it and then answer queries of the following type: given a set $A$, is it an independent set in the ...
1vote
0answers
81views
What are the fastest known parameterized algorithms for Grid Tiling?
Let $k$ and $n$ denote positive integers. In the $k$-GridTiling problem, for every pair of indices $(i,j)\in \{1, \dots, k\}^2$ we get a subset $S_{ij}\subseteq \{1, \dots, n\}^2$ of pairs of the ...
- 696
2votes
0answers
80views
Confusion with the definition of Online Set Cover
I am confused on a technicality on how Online Set Cover is defined. One way to define it is: We are given a collection of sets $\mathcal{S}$ upfront, and in each time-step an element arrives to be ...
- 649
0votes
1answer
102views
Spectral sparsification of graphs with negative edge weights
I am reading the following well-known paper on spectral sparsification of weighted graphs: https://arxiv.org/pdf/0808.4134.pdf. Page 2 contains most of the definitions relevant to this question. It is ...
- 1
14votes
1answer
2kviews
Is the 3-coloring problem NP-hard on graphs of maximal degree 3?
Consider the 3-coloring problem: given an undirected graph $G = (V, E)$, decide if there is a 3-coloring of $G$, i.e., a function $f$ from $G$ to $\{1, 2, 3\}$ such that there is no edge $\{u, v\}$ in ...
